package dp;

/**
 * @Description 剑指 Offer 10- II. 青蛙跳台阶问题
 * @Author Firenut
 * @Date 2023-01-10 22:01
 */
public class T10_numWays {

    // 方法1:动态规划
    // 定义:dp[i]表示跳到第n个台阶的跳法种数
    // 初始值: dp[0]=0,dp[1]=1
    // 递推式: dp[i]=dp[i-1]+dp[i-2] (i>1)
    public int numWays(int n) {
        if (n <= 1) {
            return 1;
        }
        long x = 1, y = 1, z;
        for (int i = 2; i <= n; i++) {
            z = (x + y) % 1000000007;
            x = y;
            y = z;
        }
//        return (int) (y %(1e9 + 7));
        return (int) y;
    }


    // 法2: 记忆型递归(划分成子问题)
    int dp[] = new int[110];
    public int numWays1(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }

        if (dp[n] == 0) {
            dp[n] = (numWays1(n - 1) + numWays1(n - 2)) % 1000000007;
            return dp[n];
        }
        return dp[n];
    }
}